public class MinMoney {
    // 兑换零钱
    // https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    public int minMoney (int[] arr, int aim) {
        // write code here
        // 完全背包问题
        // dp[i][j]表示从前i种货币中选择货币放入背包中，使得背包中总和不大于j的货币数
        int[][] dp = new int[arr.length+1][aim+1];
        int INF = 0x3f3f3f3f;
        for (int i = 1; i <= arr.length; i++) {
            dp[i][0] = INF;
        }
        for (int j = 1; j <= aim; j++) {
            dp[0][j] = INF;
        }
        for (int i = 1; i <= arr.length; i++) {
            for (int j = 0; j <= aim; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= arr[i-1]) {
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-arr[i-1]]+1);
                }
            }
        }
        return dp[arr.length][aim] == INF ? -1 : dp[arr.length][aim];
    }

    /**
     * 空间优化
     * @param arr
     * @param aim
     * @return
     */
    public int minMoney1 (int[] arr, int aim) {
        // write code here
        // 空间优化
        // 填表的时候只使用的到dp[i-1][j] dp[i][j-arr[i-1]],所以可以优化为一维数组
        int[] dp = new int[aim+1];
        int INF = 0x3f3f3f3f;
        for (int i = 1; i <= aim; i++) {
            dp[i] = INF;
        }
        for (int i = 1; i <= arr.length; i++) {
            for (int j = arr[i-1]; j <= aim; j++) {
                dp[j] = Math.min(dp[j], dp[j-arr[i-1]]+1);
            }
        }
        return dp[aim] == INF ? -1 : dp[aim];
    }
}
